package LeetCodeHot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * <p>
 * Copyright (c) 2018 Choice, Inc.
 * All Rights Reserved.
 * Choice Proprietary and Confidential.
 *
 * @author longyacao
 * @since 2024-03-25 15:44
 */
public class Hot100 {
    public static void main(String[] args) {

    }

    // 240.搜索二维矩阵II https://leetcode.cn/problems/search-a-2d-matrix-ii/?envType=study-plan-v2&envId=top-100-liked
    // 2分查找
    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = search(row, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }
    private static int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }


    // 48.旋转图像 https://leetcode.cn/problems/rotate-image/?envType=study-plan-v2&envId=top-100-liked
    // 思路：对于矩阵中第 iii 行的第 jjj 个元素，在旋转后，它出现在倒数第 iii 列的第 jjj 个位置
    public static void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }

        int[][] tmp = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                tmp[j][matrix.length - 1 - i] = matrix[i][j];
            }
        }

        // 拷贝
        for (int i = 0; i < tmp.length; i++) {
            for (int j = 0; j < tmp[i].length; j++) {
                matrix[i][j] = tmp[i][j];
            }
        }
    }

    // 54.螺旋矩阵 https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-100-liked
    // 思路：定位数组的四个顶点，模拟路径遍历，然后依次向内收缩
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }

        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.add(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.add(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }

    // 73.矩阵置0 https://leetcode.cn/problems/set-matrix-zeroes/?envType=study-plan-v2&envId=top-100-liked
    // 思路：采用了额外数组，记录了0元素的位置
    public static void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    // 41.缺失的第一个正整数 https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
    // 题目要求：时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
    // 采用原数组标记法，第一遍循环先排除0和负数，第二遍循环 利用负号标记 0 - n，取绝对值后会恢复原始值
    public static int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }

        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }

    // 238.除自身以外数组的乘积 https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked
    // 思路：构造两个数组，一个从左往右的累积，一个从右往左，计算除自身数的时候 左集合 * 右集合 即可
    public static int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        int[] answer = new int[nums.length];

        left[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            left[i] = nums[i - 1] * left[i - 1];
        }

        right[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = nums[i + 1] * right[i + 1];
        }

        // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for (int i = 0; i < nums.length; i++) {
            answer[i] = left[i] * right[i];
        }

        return answer;
    }

    // 189.轮转数组 https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked
    // 思路：第i位的数字轮转后的位置可以根据k来计算，
    public static void rotate(int[] nums, int k) {
        if (k <= 0 || nums.length == k) {
            return;
        }

        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }

    // 56.区域合并 https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
    // 思路：对原数组排序，然后轮询判断区间、插入
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0 || intervals.length == 1) {
            return intervals;
        }

        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        ArrayList<int[]> merge = new ArrayList<>();
        for (int i = 0; i < intervals.length; ++i) {
            int size = merge.size();
            if (size == 0 || merge.get(size - 1)[1] < intervals[i][0]) {
                merge.add(new int[]{intervals[i][0], intervals[i][1]});
            } else {
                merge.get(size - 1)[1] = Math.max(merge.get(size - 1)[1], intervals[i][1]);
            }
        }

        return merge.toArray(new int[merge.size()][]);
    }

    // 560.和为K的子数组 https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
    public static int subarraySum(int[] nums, int k) {
        int count = 0;
        int len = nums.length;
        for (int left = 0; left < len; left++) {
            int sum = 0;
            for (int right = left; right < len; right++) {
                sum += nums[right];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }

    // 438.找到字符串所有字母易位词 https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
    // 思路：构建固定滑动窗口，比较每段窗口的byte数组，利用只是字母的方式，构建26位数组，数组存放字母出现的次数
    public static List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<>();
        }

        List<Integer> ans = new ArrayList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i);
            }
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];
        }
        // 最后一段字符串未比较
        if (Arrays.equals(sCount, pCount)) {
            ans.add(sLen - pLen);
        }

        return ans;
    }

    // 3.无重复字符的最大子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked
    // 思路：采用滑动窗口
    public static int lengthOfLongestSubstring(String s) {
//        HashMap<Character, Integer> cache = new HashMap<>();
//        int max = 0, left = 0;
//        for (int i = 0; i < s.length(); i++) {
//            if (cache.containsKey(s.charAt(i))) {
//                left = Math.max(left, cache.get(s.charAt(i)) + 1);
//            }
//            cache.put(s.charAt(i), i);
//            max = Math.max(max, i - left + 1);
//        }
//        return max;

        Set<Character> cache = new HashSet<>();
        int right = 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i > 0) {
                cache.remove(s.charAt(i - 1));
            }

            while (right + 1 < s.length() && !cache.contains(s.charAt(right))) {
                cache.add(s.charAt(right));
                right++;
            }

            ans = Math.max(ans, right - i);
        }

        return ans;
    }

    // ?接雨水 https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
    // TODO
    public static int trap(int[] height) {
        int left = 0, right = 0, bottom = 0;
        for (int i = 0; i < height.length; i++) {
            // 找下降曲线
            if (height[i + 1] >= height[i]) {
                continue;
            }

            // 找到该下降曲线 对应的上升曲线
            for (int j = i + 1; j < height.length; j++) {

            }


        }

        return 0;
    }

    // 15.三数之和 https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
    // 思路：分3个指针进行遍历，二层指针内部采用 头尾双指针，快速筛选
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if (null == nums || nums.length < 3) {
            return result;
        }

        Arrays.sort(nums);
        // 凑 a + b +c
        // 枚举 a
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int third = nums.length - 1;
            int target = -nums[i];
            // 枚举 b
            for (int second = i + 1; second < nums.length; second++) {
                if (second > i + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }

                while (second < third && nums[second] + nums[third] > target) {
                    third--;
                }

                // 指针重合，没有找到答案
                if (second == third) {
                    break;
                }

                if (nums[second] + nums[third] == target) {
                    result.add(Arrays.asList(nums[i], nums[second], nums[third]));
                }
            }
        }
        return result;
    }

    // 11.盛水最多的容器 https://leetcode.cn/problems/container-with-most-water/?envType=study-plan-v2&envId=top-100-liked
    // 思路：左右指针分别向中遍历，长变短且面积增大的只能是增高，所以比较左右边，短边向内移动，减少复杂度
    public static int maxArea(int[] height) {
        int left = 0, right = height.length - 1, result = 0;
        while (left < right) {
            result = Math.max(Math.min(height[left], height[right]) * (right - left), result);
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return result;
    }

    // 283.移动零 https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
    // 思路：两个指针，一个主遍历，一个指向非0元素，最后将非0元素位至数组尾全部置0
    public static void moveZeroes(int[] nums) {
        int zero = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[zero] = nums[i];
                zero++;
            }
        }

        for (int i = zero; i < nums.length; i++) {
            nums[i] = 0;
        }

    }

    // 128.最长连续序列 https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
    // 思路：排序去重后遍历
    public static int longestConsecutive(int[] nums) {
        int[] array = Arrays.stream(nums).distinct().sorted().toArray();
        int tmp = nums[0];
        int tmpLength = 0;
        int maxLength = 0;
        for (int i : array) {
            if (i == tmp) {
                tmpLength++;
                tmp++;
            } else {
                tmp = i + 1;
                maxLength = Math.max(tmpLength, maxLength);
                tmpLength = 1;
            }
        }

        return Math.max(tmpLength, maxLength);
    }

    // 49.字母异位词组 https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
    // 思路：每个String进行排序后利用 hash 表的key来识别
    public static List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> cache = new HashMap<>();
        for (String str : strs) {
            byte[] bytes = str.getBytes();
            Arrays.sort(bytes);
            String key = new String(bytes);
            if (cache.containsKey(key)) {
                cache.get(key).add(str);
            } else {
                List<String> value = new ArrayList<>();
                value.add(str);
                cache.put(key, value);
            }
        }

        return cache.keySet().stream().map(cache::get).collect(Collectors.toList());
    }

    // 1.两数之和 https://leetcode.cn/problems/two-sum/?envType=study-plan-v2&envId=top-100-liked
    // 思路：利用 hash表降低算法复杂度，只需要 O(n)
    public static int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        HashMap<Integer, Integer> cache = new HashMap<>();
        for (int i = 0; i < length; i++) {
            if (cache.containsKey(target - nums[i])) {
                return new int[]{i, cache.get(target - nums[i])};
            }
            cache.put(nums[i], i);
        }
        return null;
    }
}
